#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/22
# @Author   :Changshu
# @File     :Exercise_617.py

# 617. 合并二叉树
# 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
# 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

class Solution:
	'''
	法一：深度优先
	-如果两结点为空，则返回空
	-如果一个结点为空，另一个结点不为空，则返回不为空的结点
	-如果两结点都不为空，则返回一个新结点，其值为前两个结点值的和


	def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
		if not t1:
			return t2
		if not t2:
			return t1
		root=TreeNode(t1.val+t2.val)
		root.left=self.mergeTrees(t1.left,t2.left)
		root.right=self.mergeTrees(t1.right,t2.right)
		return root
	'''


	'''法二：广度优先
	使用3个队列存储
	'''
	def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
		if not t1:
			return t2
		if not t2:
			return t1
		queue1,queue2=[t1],[t2]
		res=[]
		while queue1 or queue2:
			node1,node2=None,None
			if queue1:
				node1=queue1.pop(0)
			if queue2:
				node2 = queue2.pop(0)
			if node1:
				queue1.append(node1.left)
				queue1.append(node1.right)
			if node2:
				queue2.append(node2.left)
				queue2.append(node2.right)
			if node1 and node2:
				res.append(TreeNode(node1.val+node2.val))
			elif node1 and not node2:
				res.append(TreeNode(node1.val))
			elif not node1 and node2:
				res.append(TreeNode(node2.val))
			else:
				res.append(None)
		count=0
		while count<len(res):
			node=res[count]
			if node:
				if 2*count+1<len(res):
					node.left=res[2*count+1]
				else:
					node.left = None
				if 2*count+2<len(res):
					node.right=res[2*count+2]
				else:
					node.right = None
			count+=1
		return res[0]

	def preOrder(self,root:TreeNode):
		if not root:
			return
		print(root.val,end=' ')
		self.preOrder(root.left)
		self.preOrder(root.right)




if __name__ == '__main__':
	root1=TreeNode(1)
	node2_1 = TreeNode(3)
	node2_2 = TreeNode(2)
	node3_1 = TreeNode(5)
	root1.left=node2_1
	root1.right=node2_2
	node2_1.left=node3_1

	root2=TreeNode(2)
	n2_1= TreeNode(1)
	n2_2= TreeNode(3)
	n3_1= TreeNode(4)
	n3_2= TreeNode(7)
	root2.left=n2_1
	root2.right=n2_2
	n2_1.right=n3_1
	n2_2.right=n3_2

	solution=Solution()
	root=solution.mergeTrees(root1,root2)
	solution.preOrder(root)



